#include <iostream>
#include <map>
#include <vector>
#include <fstream>
#include <string>
#include <set>
using namespace std;
vector<string> inputBuffer;
map<string, int> nameHash;
ofstream lout("first.log");
struct TERM {
    string name;
    bool isTerm;
    vector<vector<string> > expan;
    set<string> firstSet;
    TERM() {
        name = "";
        expan.clear();
    }
    TERM(string _name, bool _isTerm) {
        name = _name;
        isTerm = _isTerm;
        firstSet.clear();
        if (isTerm) firstSet.insert(name);
        expan.clear();
    }
};
vector<TERM> generators;
int nonStart, nonEnd;
void init()
{
    generators.clear();
    nameHash.clear();
    ifstream fin("shell-BNF.txt");
    string temp;
    while (!fin.eof()) {
        fin >> temp;
        if ("/*" == temp) {
            while ("*/" != temp) fin >> temp;
            continue;
        }
        inputBuffer.push_back(temp);
    }
}

void showTokens()
{
    int size = inputBuffer.size();
    for (int i=0; i<size; ++i) {
        lout << inputBuffer[i] << " ";
    }
    lout << endl;
}

void showTerminals()
{
    int size = generators.size(), i;
    for (i=0; i<size; ++i) {
        lout << "name: " << generators[i].name << "{" << endl;
        lout << "     isTerm: " << generators[i].isTerm << endl;
        lout << "     firstSet: ";
        set<string>::iterator sit;
        for (sit=generators[i].firstSet.begin(); sit!=generators[i].firstSet.end(); ++sit) {
            lout << *sit << " ";
        }
        lout << endl << "}" << endl;
    }
}

int getAllTerminals()
{
    int i = -1, index;
    while (true) {
        ++i;
        string cur = inputBuffer[i];
        if ("======" == cur) {
            break;
        }
        if ("%token" == cur) continue;
        TERM term(cur, true);
        index = generators.size();
        nameHash.insert(pair<string, int>(cur, index));
        generators.push_back(term);
    }
    nonStart = index + 1;
    return ++i;
}

void getGenerator(int startIndex)
{
    int nonIndex, size = inputBuffer.size(), index = startIndex;
    string tmp;
    while (index < size - 1) {
        string curLeft = inputBuffer[index];
        TERM term(curLeft, false);
        index += 2; // skip ':'
        vector<string> right; right.clear();
        while (index < size) {
            if (";" == inputBuffer[index]) {
                if ("|" == inputBuffer[index-1]) {
                    string strEps = "EMPTY";
                    right.push_back(strEps);
                    term.firstSet.insert(strEps);
                }
                term.expan.push_back(right);
                ++index;
                break;
            } else if ("|" == inputBuffer[index]) {
                term.expan.push_back(right);
                ++index;
                right.clear();
            } else {
                right.push_back(inputBuffer[index]);
                ++index;
            }
        }
        nonIndex = generators.size();
        generators.push_back(term);
        nameHash.insert(pair<string, int>(curLeft, nonIndex));
    }
    nonEnd = generators.size();
}

void showGenerator()
{
    int size = generators.size(), i;
    for (i=0; i<size; ++i) if (!generators[i].isTerm) {
        lout << i << ": " << generators[i].name << " := " << endl;
        int ss = generators[i].expan.size(), t;
        for (t=0; t<ss; ++t) {
            lout << "  ";
            int ssize = generators[i].expan[t].size(), k;
            for (k=0; k<ssize; ++k) {
                lout << generators[i].expan[t][k] << "  ";
            }
            lout << endl;
        }
        lout << endl;
    }
    lout << "nonStart: " << nonStart << endl;
    lout << "nonEnd: " << nonEnd << endl;
}

void unionSet(set<string> &a, set<string> &b)
{
    set<string>::iterator sit;
    for (sit=b.begin(); sit!=b.end(); ++sit) {
        a.insert(*sit);
    }
}

void showTerm(const TERM &term)
{
    lout << "term: " << term.name << "{ " << endl;
    lout << "\tisTerm: " << term.isTerm << endl;
    lout << "\tfirstSet: ";
    set<string>::iterator sit;
    for (sit=term.firstSet.begin(); sit!=term.firstSet.end(); ++sit) {
        lout << *sit << " ";
    }
    lout << endl;
    lout << "\tgen: " << endl;
    for (int i=0; i<term.expan.size(); ++i) {
        lout << i + 1 << ": ";
        for (int t=0; t<term.expan[i].size(); ++t) {
            lout << term.expan[i][t] << " ";
        }
        lout << endl;
    }
    lout << endl;
}

void showSet(const set<string> s)
{
    set<string>::iterator sit;
    for (sit=s.begin(); sit!=s.end(); ++sit) {
        lout << *sit << " ";
    }
    lout << endl;
}

void getAllFirstSet()
{
    bool changed = true;
    int times = 100;
    while (changed) {
        changed = false;
        int index;
        // for each non-terminal
        for (index=nonStart; index<nonEnd; ++index) {
            TERM curTerm = generators[index];
            int i, genSize = curTerm.expan.size();
            // for each right-part
            int record = curTerm.firstSet.size();
            // lout << "name: " << curTerm.name << ": " << endl;
            // showTerm(curTerm);
            for (i=0; i<genSize; ++i) {
                vector<string> right = curTerm.expan[i];
                int t, size = right.size();
                // for each right-part term
                for (t=0; t<size; ++t) {
                    int termId = nameHash[right[t]];
                    // lout << right[t] << " => " << termId;
                    TERM tm = generators[termId];
                    // showSet(tm.firstSet);
                    // showTerm(tm);
                    unionSet(curTerm.firstSet, tm.firstSet);
                    if (tm.firstSet.find("EMPTY") == tm.firstSet.end()) break;
                }
            }
            if (curTerm.firstSet.size() != record) changed = true;
            generators[index] = curTerm;
            // showSet(generators[index].firstSet);
            // lout << endl;
        }
    }
}

void printOut()
{
    for (int index=nonStart; index<nonEnd; ++index) {
        lout << generators[index].name << ": ";
        showSet(generators[index].firstSet);
        lout << endl;
    }
}

int main()
{
    init();
    int index = getAllTerminals();
    getGenerator(index);
    getAllFirstSet();
    printOut();

    return 0;
}

